#include <vector>
#include <set>
#include <algorithm>
#include <type_traits>
#include <climits>

class Solution
{
public:
	int maxSumSubmatrix(std::vector<std::vector<int>>& matrix, int k)
	{
		int nRow = matrix.size();
		int nCol = nRow==0 ? 0 : matrix[0].size();
		if (nRow > nCol) {
			std::vector<std::vector<int>> tmp(nCol, std::vector<int>(nRow));
			for (int r = 0; r < nRow; r++)
				for (int c = 0; c < nCol; c++)
					tmp[c][r] = matrix[r][c];
			matrix = std::move(tmp);
			std::swap(nRow, nCol);
		}

		std::vector<int> s(nCol, 0);
		for (auto& row : matrix) {
			std::transform(s.cbegin(), s.cend(), row.cbegin(), s.begin(), [](int a, int b) { return a + b; });
			std::copy(s.cbegin(), s.cend(), row.begin());
		}

		int globalBest = std::numeric_limits<int>::min();
		for (int i = -1; i < nRow - 1; i++) {
			for (int j = i + 1; j < nRow; j++) {
				std::vector<int> s(nCol);
				if (i == -1) std::copy(matrix[j].cbegin(), matrix[j].cend(), s.begin());
				else std::transform(matrix[j].cbegin(), matrix[j].cend(), matrix[i].cbegin(), s.begin(), [](int a, int b) { return a - b; });
				int acc = 0;
				int best = std::numeric_limits<int>::min();
				std::set<int> sub;
				sub.insert(0);
				for (auto e : s) {
					acc += e;
					auto itr = sub.lower_bound(acc - k);
					if (itr != sub.cend()) best = std::max(best, acc - *itr);
					sub.insert(acc);
				}
				globalBest = std::max(globalBest, best);
			}
		}
		return globalBest;
	}
};